import java.util.HashMap;
import java.util.Map;

/**
 * 454. 四数相加 II
 * https://leetcode-cn.com/problems/4sum-ii/
 */
public class Solutions_454 {
    public static void main(String[] args) {
        int[] A = {1, 2};
        int[] B = {-2, -1};
        int[] C = {-1, 2};
        int[] D = {0, 2};  // output: 2

        int result = fourSumCount(A, B, C, D);
        System.out.println(result);
    }

    /**
     * 解题思路：划分为两个区域，其中一个区域存储结果，另一个区域来查询结果
     * 两两组合，将 A 与 B 所有元素组合相加，得到的结果存储到 map 中
     * 再计算 C 与 D 所有元素组合相加，若相加后的值的负数，在 map 中存在，说明四个数相加为 0
     */
    public static int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        // key：相加的和，value：和的次数
        Map<Integer, Integer> map = new HashMap<>();
        int res = 0;
        for (int a : A) {
            for (int b : B) {
                int sum = a + b;
                // 和与其出现次数，记录到 map 中
                map.put(sum, map.getOrDefault(sum, 0) + 1);
            }
        }
        for (int c : C) {
            for (int d : D) {
                int sum = c + d;
                // 获取 map 中 -sum 的出现次数，因为 sum + (-sum) = 0
                res += map.getOrDefault(-sum, 0);
            }
        }
        return res;
    }
}
